package com.lw.leetcode.tree.b;

import com.lw.leetcode.tree.TreeNode;

import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * <p>
 * tree
 * b
 * 剑指 Offer II 055. 二叉搜索树迭代器
 * 173. 二叉搜索树迭代器
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/19 13:20
 */
public class BSTIterator {

    public static void main(String[] args) {
        TreeNode instance = TreeNode.getInstance5();
        BSTIterator test = new BSTIterator(instance);
        while (test.hasNext()) {
            System.out.println(test.next());
        }
    }


    private Stack<TreeNode> stack = new Stack<>();

    public BSTIterator(TreeNode root) {
        while (root != null) {
            stack.add(root);
            root = root.left;
        }
    }

    public int next() {
        TreeNode pop = stack.pop();
        int val = pop.val;
        if (pop.right != null) {
            pop = pop.right;
            while (pop != null) {
                stack.add(pop);
                pop = pop.left;
            }
        }
        return val;
    }

    public boolean hasNext() {
        return !stack.isEmpty();
    }

}
